function new_game() {
}

/*function make_move() {
   var board = get_board();
	
   // we found an item! take it!
   if (board[get_my_x()][get_my_y()] > 0) {
       return TAKE
   }
   
   var rand = Math.random() * 4;

   if (rand < 1) return NORTH;
   if (rand < 2) return SOUTH;
   if (rand < 3) return EAST;
   if (rand < 4) return WEST;

   return PASS;
}*/

var nearest_fruit_location_x = -5555;
var nearest_fruit_location_y = -5555;
var nearest_fruit_distance = 100000;
var cur_location_x;
var cur_location_y;

var checked_squares = new Array(HEIGHT);
var open_squares_grid = new Array(HEIGHT);
var open_squares;
var fruit_count = new Array();

var CHECKED = 1;
var MARKED_FOR_EXPAND = 1;

function make_move() {
   var board = get_board();
   
   for(var count = 1; count <= get_number_of_item_types(); count++){
	  fruit_count[count] = get_total_item_count(count);
   }
   
   // we found an item! take it!
   if (board[get_my_x()][get_my_y()] > 0) {
      if(get_my_x() === nearest_fruit_location_x && get_my_y() === nearest_fruit_location_y){
         nearest_fruit_location_x = -5555;
	     nearest_fruit_location_y = -5555;
	     nearest_fruit_distance = 100000;
	  }
	  fruit_count[board[get_my_x()][get_my_y()]]--;
      return TAKE
   }
	
   cur_location_x = get_my_x();
   cur_location_y = get_my_y();
   open_squares = new Array();
   init_arrays();
   return find_fruit(cur_location_x, cur_location_y);
}

function get_min_type(){
   var min_fruit_type = 1;
   for(var count = 1; count <= (fruit_count.length)-1; count++){
	  if(fruit_count[count+1] < fruit_count[count] || fruit_count[count] === 0){
	     min_fruit_type = count+1;
	  }
   }
   return min_fruit_type;
}

function find_fruit(x, y){
   var min_fruit_type = get_min_type();
   
   if(nearest_fruit_location_x != -5555){
       var board = get_board();
	   if(board[nearest_fruit_location_x][nearest_fruit_location_y] > 0){
	      //find path to nearest fruit
	      return find_path([cur_location_x, cur_location_y],[nearest_fruit_location_x, nearest_fruit_location_y]);
	   }else{
	      //fruit has been taken by the opponent, reset variables and look for nearest fruit
	      nearest_fruit_location_x = -5555;
		  nearest_fruit_location_y = -5555;
		  nearest_fruit_distance = 100000;
	   }
   }
   var adjacent_squares = [ 
						[x-1, y], [x-1, y+1], [x, y+1], [x+1, y+1],
						[x+1, y], [x+1, y-1], [x, y-1], [x-1, y-1]
					  ];
	for(var ctr=0; ctr < 8; ctr++){
	   var tempx = adjacent_squares[ctr][0];
	   var tempy = adjacent_squares[ctr][1];
	   //check if square is out of board
	   if(tempx < 0 || tempx > WIDTH-1 || tempy < 0 || tempy > HEIGHT-1){
          continue;
	   }
	   //store for expansion in search of fruit
	   if(open_squares_grid[adjacent_squares[ctr][0]][adjacent_squares[ctr][1]] != MARKED_FOR_EXPAND){
	      open_squares_grid[adjacent_squares[ctr][0]][adjacent_squares[ctr][1]] = MARKED_FOR_EXPAND;
	      open_squares[open_squares.length] = [adjacent_squares[ctr][0], adjacent_squares[ctr][1]];
	   }
	   //test current adjacent square for presence of fruit, if it hasn't been tested
	   if(checked_squares[adjacent_squares[ctr][0]][adjacent_squares[ctr][1]] != CHECKED){
	      //mark square as checked for fruit
	      checked_squares[adjacent_squares[ctr][0]][adjacent_squares[ctr][1]] = CHECKED;
	      var is_fruit = fruit_exists(adjacent_squares[ctr][0], adjacent_squares[ctr][1]);
	      if(is_fruit && board[adjacent_squares[ctr][0]][adjacent_squares[ctr][1]] === min_fruit_type){	  
		     var distance_to_fruit = Math.round(10 * Math.sqrt(Math.pow(adjacent_squares[ctr][0] - cur_location_x, 2) + Math.pow(adjacent_squares[ctr][1] - cur_location_y, 2)));
		     if(distance_to_fruit < nearest_fruit_distance){
		        nearest_fruit_location_x = adjacent_squares[ctr][0];
		        nearest_fruit_location_y = adjacent_squares[ctr][1];
			    nearest_fruit_distance = distance_to_fruit;
		     }
	      }  
	   }
	}
	if(nearest_fruit_location_x != -5555){
	   //find path to nearest fruit
	   return find_path([cur_location_x, cur_location_y],[nearest_fruit_location_x, nearest_fruit_location_y]);
	}else{
	   //no fruit in the adjacent squares. expand search using the next node in open_square
	   square = open_squares.shift();
	   return find_fruit(square[0], square[1]);
	}
}

function find_path(src, dest){
   var adj_squares = [ 
						[src[0]-1, src[1]], [src[0]-1, src[1]+1], [src[0], src[1]+1], [src[0]+1, src[1]+1],
						[src[0]+1, src[1]], [src[0]+1, src[1]-1], [src[0], src[1]-1], [src[0]-1, src[1]-1]
					  ];
   //find the adjacent square with the least distance to destination. return move
   var min_distance = 500000;
   var direction = null;
   for(var ctr=0; ctr<8; ctr++){
      var distance_to_fruit = Math.round(10 * Math.sqrt(Math.pow(adj_squares[ctr][0] - dest[0], 2) + Math.pow(adj_squares[ctr][1] - dest[1], 2)));
	  
	  if(distance_to_fruit < min_distance){
	     min_distance = distance_to_fruit;
		 if(adj_squares[ctr][0] === src[0]-1){
	        direction = WEST;
	     }
            if(adj_squares[ctr][0] === src[0]+1){
	        direction = EAST;
	     }
	     if(adj_squares[ctr][0] === src[0]){
	        switch(adj_squares[ctr][1]){
		       case src[1]+1:
			      direction = SOUTH;break;
			   case src[1]-1:
			      direction = NORTH;break;
		    }
	     }
	  }
   }
   return direction;
}

function fruit_exists(x, y){
   if(x < 0 || x > WIDTH-1 || y < 0 || y > HEIGHT-1){
      return false;
   }
   var board = get_board();
   if (board[x][y] > 0) {
       return true;
   }
   return false;
}  

//initialize arrays for keeping track of squares 
//that have already been checked for fruit and for expanding search
function init_arrays(){
   for(var row = 0; row < HEIGHT; row++){
      checked_squares[row] = new Array(WIDTH);
	  open_squares_grid[row] = new Array(WIDTH);
      for(var col = 0; col < WIDTH; col++){
	     checked_squares[row][col] = -1;
		 open_squares_grid[row][col] = -1;
	  }
   }
}
